<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>封装单向链表</title>
</head>

<body>
    <script>
        // 封装链表类
        function LinkedList() {
            function Node(data) {
                // 封装一个内部的类： 节点类
                this.data = data
                this.next = null
            }

            // 属性
            this.head = null
            this.length = 0

            // 1. 追加方法
            LinkedList.prototype.append = function (data) {
                // 1.创建新的节点
                var newNode = new Node(data)  // 不管是不是第一个节点，都要先创建下新节点
                // 2. 判断是否添加的是第一个节点（只有一个节点的时候）
                if (this.length == 0) { // 2.1 添加的是第一个节点
                    this.head = newNode  // 将head指向新节点
                } else {               // 2.2 添加的不是第一个节点
                    // 找到最后一个节点
                    var current = this.head  // 让head指向 current
                    while (current.next) {    // 如果current的下一个节点不为空
                        current = current.next  // 让current指向下一个节点--直至最后next为空
                    }

                    // 最后让节点的next指向新的节点
                    current.next = newNode
                }
                // 3. 添加完节点后，链表的长度要加1
                this.length += 1
            }

            // 2. 实现toString() 方法
            LinkedList.prototype.toString = function () {
                // 1.定义变量
                var current = this.head
                var listString = ''

                // 2. 循环获取一个个节点
                while (current) {
                    // 2.1 将遍历的current里面的data放入到listString中
                    listString += current.data + ' '
                    // 2.2 更新current的指向，避免成为死循环
                    current = current.next

                }
                return listString
            }

            // 根据下标删除元素
            LinkedList.prototype.insert = function (position, data) {
                //理解positon的含义：position=0表示新界点插入后要成为第1个节点，position=2表示新界点插入后要成为第3个节点
                //1.对position进行越界判断:要求传入的position不能是负数且不能超过LinkList的length
                // 1.检测越界问题: 越界插入失败
                if (position < 0 || position > this.length) return false

                // 2.找到正确的位置, 并且插入数据
                //2.根据data创建newNode
                var newNode = new Node(data)
                var current = this.head
                var previous = null
                index = 0

                // 3.判断是否列表是否在第一个位置插入
                //3.插入新节点
                //情况1：插入位置position=0
                if (position == 0) {
                    // 让新节点指向第一个节点
                    newNode.next = current
                    // 让head指向新节点
                    this.head = newNode
                } else {   // //情况2：插入位置position>0(该情况包含position=length)
                    while (index++ < position) {   //  //步骤1：通过while循环使变量current指向position位置的后一个节点(注意while循环的写法)
                        //步骤2：在current指向下一个节点之前，让previous指向current当前指向的节点
                        previous = current
                        current = current.next
                    }
                    // 步骤3：通过变量current(此时current已经指向position位置的后一个节点)，使newNode指向position位置的后一个节点
                    newNode.next = current
                    //步骤4：通过变量previous，使position位置的前一个节点指向newNode
                    previous.next = newNode
                }
                /*
            启示：
            1.我们无法直接操作链表中的节点，但是可以通过变量指向这些节点，以此间接地操作节点(替身使者)；
            比如current指向节点3，想要节点3指向节点4只需要：current.next = 4即可。
            2.两个节点间是双向的，想要节点2的前一个节点为节点1，可以通过：1.next=2，来实现；
          */

                // 4.length+1
                //4.新节点插入后要length+1
                this.length += 1

                return true
            }

            // 4. get()方法
            LinkedList.prototype.get = function (position) {
                // 1. 边界判断
                if (position < 0 || position >= this.length) return null

                // 2. 获取对应的data
                var current = this.head
                var index = 0
                /* position = 2
                index=0 current = 
                index=1 current = 
                index = 2 终止while循环
                
                */
                while (index++ < position) {
                    current = current.next
                }
                return current.data

            }

            // 5。 indexOf方法  ----通过传入data 来查找对应的索引
            LinkedList.prototype.indexOf = function (data) {
                // 1. 定义变量，保存信息
                var current = this.head
                var index = 0

                // 2. 找到元素所在的位置
                while (current) {
                    if (current.data === data) {
                        return index
                    } else {
                        current = current.next
                        index += 1
                    }
                }
                // 3. 来到这个位置，说明没有找到，则返回-1
                return -1
            }


            // 6.update方法
            LinkedList.prototype.update = function (position, newData) {
                // 1.越界判断
                if (position < 0 || position >= this.length) return false
                // 2. 先查找正确的节点
                var current = this.head
                var index = 0;
                while (index++ < position) {
                    current = current.next
                }
                // 3.将position位置的node上的data修改成newDate
                current.data = newData

                return true

            }

            // 7. removeAt方法------根据索引删元素
            LinkedList.prototype.removeAt = function (position) {
                // 1.越界判断
                if (position > 0 || position >= this.length) return null

                // 2. 判断是否删除的是第一个节点
                // 定义变量，保存信息
                var current = this.head
                if (position === 0) {
                    this.head = this.head.next
                } else {
                    var index = 0
                    var previous = null
                    // var current = this.head
                    while (index++ < position) {
                        // 同步更新---- previous 和 current
                        previous = current
                        current = current.next
                    }

                    // 前一个节点的next指向 current的next即可
                    previous.next = current.next
                }

                // 3. length-1
                this.length -= 1
                // 4. 返回移除的数据
                return current.data

            }

            // 8.remove方法
            LinkedList.prototype.remove = function (data) {
                // 1. 获取data在列表中的位置
                var position = this.indexOf(data)
                // 2. 根据位置信息，删除节点
                return this.removeAt(position)
            }

            // 9. isEmpty方法
            LinkedList.prototype.isEmpty = function () {
                return this.length == 0
            }

            // 10. size()方法
            LinkedList.prototype.size = function () {
                return this.length
            }



        }

        //测试代码
        //1.创建LinkList
        var list = new LinkedList()

        //2.插入数据---向列表尾部插入一个新的项
        list.append('aaa')
        list.append('bbb')
        list.append('ccc')
        // alert(list)

        //3.测试insert方法---向列表特定位置插入一个新的项
        list.insert(0, 'AAA');    // 在链表最前面插入节点
        list.insert(2, 'BBB');    // 在链表中第二个节点后插入节点
        list.insert(5, 'CCC');    // 在链表最后插入节点
        // alert(list);
        console.log(list);

        // // 测试get方法--通过索引，获取对应元素
        // alert(list.get(0)) // 得到位置为0上的元素
        // alert(list.get(2))


        // 测试indexOf方法----- 返回对应的索引
        // alert(list.indexOf('aaa'))  // 1
        // alert(list.indexOf('BBB'))  // 2
        // alert(list.indexOf('FFF'))  // -1 

        // 测试update方法
        list.update(0, 'GGG')
        console.log(list.toString());   //GGG aaa BBB bbb ccc CCC
        list.update(5, 'YYY')
        console.log(list.toString());   // GGG aaa BBB bbb ccc YYY

        // // 测试removeAt方法
        console.log('---------分隔符---------')
        list.removeAt(5)
        console.log(list.toString())      //  GGG aaa BBB bbb ccc YYY
        list.removeAt(0)
        console.log(list.toString())      //  aaa BBB bbb ccc YYY


        console.log('---------分隔符---------')
        // 测试remove方法
        list.remove('BBB')
        console.log(list.toString());
        list.remove('YYY')
        console.log(list.toString());

        // 测试isEmpty()方法
        // console.log(list.isEmpty())   // false

        // // 测试size方法
        // console.log(list.size())    // 5





    </script>

</body>

</html>